package someTestExcemple.huaweiOd.sort;
//华为OD机试 - 第k个排列 - 全排列递归（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/132942869
import java.util.*;
public class FullPermutationRecursion {
    private static int count=0;
    private static String result = "";
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        System.out.println(getKthPermutation(n, k));

        //2.深度优先遍历，时间复杂度O(n!)
        boolean[] used = new boolean[n + 1];
        dfs(new StringBuilder(), used, n, k);
        System.out.println(result);
    }

/*    具体规律分析与证明
1. 以固定数字开头的排列数量
    考虑以某个数字开头的排列情况。当确定了排列的最高位数字后，剩下的 n - 1 个数字的全排列数为 (n - 1)!。例如，当 n = 3 时，以 1 开头的排列有 (3 - 1)! = 2! = 2 种，分别是 “123” 和 “132”；以 2 开头的排列也有 2 种，分别是 “213” 和 “231”；以 3 开头的排列同样有 2 种，分别是 “312” 和 “321”。
    这是因为对于固定的最高位数字，剩下的 n - 1 个数字进行全排列，根据全排列的公式，其排列数为 (n - 1)!。
            2. 确定最高位数字
    设我们要找第 k 个排列（这里 k 从 1 开始计数），为了方便计算，先将 k 转换为 0 索引，即 k = k - 1。
    通过计算 index = k / (n - 1)!，可以确定最高位数字在剩余数字集合中的索引。这里的 index 表示第 k 个排列的最高位数字是剩余数字集合中第 index 小的数字。
    证明：
    假设 k 是一个在 [0, n! - 1] 范围内的整数。由于以每个数字开头的排列有 (n - 1)! 个，那么 k / (n - 1)! 就表示 k 所在的以某个数字开头的排列组的编号。例如，当 n = 3 时，(n - 1)! = 2，如果 k = 2（转换为 0 索引后 k = 1），1 / 2 = 0，说明第 2 个排列（0 索引）是以剩余数字集合中第 0 小的数字（即 1）开头的排列组中的某个排列。
            3. 确定后续位数字
    在确定了最高位数字后，将该数字从剩余数字集合中移除，此时问题就转化为在剩下的 n - 1 个数字中找第 k % (n - 1)! 个排列。
    证明：
    因为 k 可以表示为 k = q × (n - 1)! + r，其中 q = k / (n - 1)! 是商，r = k % (n - 1)! 是余数。q 确定了最高位数字，而 r 表示在以该最高位数字开头的 (n - 1)! 个排列中，第 k 个排列是第 r 个。所以，在确定了最高位数字后，问题就变成了在剩下的 n - 1 个数字的全排列中找第 r 个排列，即 k % (n - 1)! 个排列。
            4. 重复上述过程
    不断重复步骤 2 和步骤 3，依次确定每一位数字，直到确定了所有 n 位数字，就得到了第 k 个排列。*/
    public static String getKthPermutation(int n, int k) {
        // 初始化数字列表
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        // 计算阶乘
        int[] factorial = new int[n];
        factorial[0] = 1;
        for(int i=1;i<n;i++) {
            factorial[i] = factorial[i-1] * i;
        }

        // 调整k为0索引
        k -= 1;

        StringBuilder result = new StringBuilder();
        for(int i = n-1; i >=0; i--) {
            int idx = k / factorial[i];
            result.append(numbers.get(idx));
            numbers.remove(idx);
            k %= factorial[i];
        }

        return result.toString();
    }

    private static void dfs(StringBuilder current, boolean[] used, int n, int k) {
        if (current.length() == n) {
            count++; //此时+1表示//生成了一个完整的排序
            if (count == k) { //目标排列
                result = current.toString();
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!used[i]) {
                used[i] = true;
                current.append(i);
                dfs(current, used, n, k);
                //已经找到了目标排列，不用在继续下一轮dfs了
                if (count == k) {
                    return;
                }
                used[i] = false;
                current.deleteCharAt(current.length() - 1);
            }
        }
    }
}
